package LeetCode._01_树;
/**
 * https://leetcode-cn.com/problems/diameter-of-binary-tree/
 */
public class _543_二叉树的直径 {
    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;
        TreeNode() {}
        TreeNode(int val) { this.val = val; }
        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    int maxZj = 0;
    //函数定义：输入一个节点，返回它的最大直径
    public int diameterOfBinaryTree(TreeNode root) {
        maxDepth(root);
        return maxZj;

    }
    //计算输入节点的最大深度
    public int maxDepth(TreeNode root) {
        if(root == null){ //base case
            return 0;
        }

        //左子树的最大深度
        int left = maxDepth(root.left);
        //右子树的最大深度
        int right = maxDepth(root.right);

        //当前节点的最大直径
        int myDepth = left + right;
        //记录整棵树的最大直径
        maxZj = Math.max(myDepth,maxZj);

        //返回该节点的最大深度
        return 1 + Math.max(left,right);
    }

}
